package com.tlvip.arithmetic.ch04;

/**
 * <p>description：约瑟夫问题</p>
 * <p>copyright： copyright(C)2016-2099</p>
 * <p>Life is short,we need passion</p>
 * <p>Summary： </p>
 * <p>instructions： </p>
 * Date 1/24/21</p>
 * Author mac
 *
 * @version 1.0
 */
public class YSFProblem {
    YSFNode head;
    YSFNode tail;
    int size = 0;

    /**
     * 采用头插法
     *
     * @param value
     */
    public void insert(String value) {
        YSFNode ysfNode = new YSFNode(value);
        // head空时，head = tail = 新节点
        if (head == null) {
            head = ysfNode;
            tail = ysfNode;
        } else {
            // 新节点的next指向原head
            ysfNode.next = head;
            // 原head向新节点移动
            head = ysfNode;
            // 尾节点的next指向新的head，行成环
            tail.next = head;
        }
        size++;
    }

    public String delete(int position) {
        String value = null;
        YSFNode<String> current = head;
        for (int i = 1; i < position - 1; i++) {
            current = current.next;
        }
        value = (String) current.next.value;
        current.next = current.next.next;
        size--;
        return value;
    }

    public void update(String value, int position) {
        YSFNode current = head;
        for (int i = 1; i < position; i++) {
            current = current.next;
        }
        current.value = value;
    }

    public String get(int position) {
        YSFNode<String> current = head;
        for (int i = 1; i < position; i++) {
            current = current.next;
        }
        return current.value;
    }

    public void print() {
        YSFNode<String> current = head;
        for (; ; ) {
            System.out.print(current.value + "  ");
            current = current.next;
            if (current.next == head) {
                System.out.println(current.value);
                break;
            }
        }
        System.out.println();
    }

    /**
     * 输出约瑟夫
     *
     * @param interval
     */
    public void printYSF(int interval) {
        YSFNode current = head;
        int batch = 0;
        // 如果只剩下一个节点，那么就跳出循环
        while (current.next != current) {
            // 统计执行了多少次
            batch++;
            // 用单向环形列表，需要将指针设置到待删除节点的前置节点（i < interval - 2），便于操作。
            for (int i = 0; i < interval - 2; i++) {
                current = current.next;
            }
            // current.next是被干掉的节点
            System.out.println("第" + batch + "次干掉:" + current.next.value + ";从" + current.next.next.value + "开始");
            // 重置head
            if (current.next == head) {
                head = current.next.next;
            }
            // 重置tail
            if (current.next == tail) {
                tail = current;
            }
            // 断开被干掉的节点，连接被干掉的节点的前置节点和后置节点
            current.next = current.next.next;
            // 当前节点指向下一个节点，并重新计数：执行for循环
            current = current.next;
            print();
        }
        System.out.println("最后幸存者:" + current.value);
    }

    public static void main(String[] args) {
        YSFProblem ysfProblem = new YSFProblem();
        for (int i = 1; i < 11; i++) {
            ysfProblem.insert(String.valueOf(i));
        }
        ysfProblem.print();
//        ysfProblem.delete(2);
//        ysfProblem.print();
//        ysfProblem.update("99", 4);
//        ysfProblem.print();
//        System.out.println(ysfProblem.get(5));
        ysfProblem.printYSF(3);
    }


}

class YSFNode<T> {
    T value;
    YSFNode next;

    public YSFNode(T value) {
        this.value = value;
        this.next = null;
    }
}
